package imooc_math.sort;

import java.util.Arrays;

import resource.SortTestHelper;

public class QuickSort {
	//没有优化之前：在对近乎相同的数据进行排序时，数组的两边会不平衡，退化成O（n^2）的时间复杂度
	//对数组的[l,r]范围进行排序
	//partition	n划分;分开
	private static int partition(Comparable[] arry,int l,int r){
		int exchangeIndex=(int)(Math.random()*(r-l+1))+l;//快排的优化：将数组索引为l位置的值与[l,r]任意位置的值进行交换，保证arry[l]在整个数组中最小的概率极其小
		swap(arry,l,exchangeIndex);//为什么要做这个优化：因为在对近乎有序的数组进行排序时，很可能出现[l,r]范围内l最小。如果每次索引为l的值都是最小的话，快速排序就会退化成O（n^2）的算法
		int j=l;
		Object v=arry[l];//进行比较的数
		//[l,j][j+1,r]这两部分进行排序。并不能保证[l,j]与[j+1,r]数组内部的顺序，只能保证左半部分总体小于右半部份
		for(int i=l+1;i<=r;i++){//1--r（遍历r-1+1次）（默认l=0）
			if(arry[i].compareTo(v)<0){
				swap(arry,j+1,i);//在最后一次遍历的时候，前边已经遍历了r-1次，假设他每次都满足if语句条件从而++，最后一次遍历的时候，j+1=0+r-1+1，可以取到
				j++;//左部分长度加一x
				/*swap(arry,qian,i);
				qian++;*/
			}
		}
		swap(arry,j,l);
		return j;
	}
	private static void sort(Comparable[] arry,int l,int r){
		if(l>=r){
			return;
		}
		int j=partition(arry,l,r);
		//int j=sort(arry,0,arry.length-1);
		sort(arry,l,j);
		sort(arry,j+1,r);
	
	}
	public static Object[] sort(Comparable[] arry){
		int n=arry.length;
		sort(arry,0,n-1);	
		return arry;
	}
	public static void swap(Object [] arr,int a,int b){
		Object t=arr[a];
		arr[a]=arr[b];
		arr[b]=t;
	}
	public static void main(String[] args) {
		/*Integer[] a=new SortTestHelper().generateRandomArray(30, 0, 100);
		
		System.out.println(Arrays.toString(a));
		System.out.println(Arrays.toString(sort(a)));*/
		/*int n=1000000;
		Integer[] arry=new  SortTestHelper().generateRandomArray(n, 0, n);
		SortTestHelper sth=new SortTestHelper();
		Integer[] arryCopy=Arrays.copyOf(arry,arry.length);
		sth.testSort("imooc_math.QuickSort", arryCopy);
		sth.testSort("imooc_math.MergeSort", arry);*/
		
		/*int n=30000;
		int swapTimes=10;
		Integer[] arry=new  SortTestHelper().generateNearlyOrderedArray(n, swapTimes);
		SortTestHelper sth=new SortTestHelper();
		Integer[] arryCopy=Arrays.copyOf(arry,arry.length);
		
		sth.testSort("imooc_math.MergeSort", arry);
		sth.testSort("imooc_math.QuickSort", arryCopy);//在对近乎有序的数组进行排序时，快速排序的时间复杂度可能会退化成O(n^2)，比归并排序慢很多
		 */
	}
}
